Матч 349, Обнаружение радаром (RadarFinder)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Два радара измеряют расстояние до цели. Известны местоположения радаров (x₁, y₁) и (x₂, y₂), а также вычисленные ими расстояния до цели r₁ и r₂. Необходимо определить количество возможных местоположений врага. Если их существует бесконечно много, то вернуть -1.

Класс: RadarFinder

Метод: int possibleLocations(int x1, int y1, int r1,

int x2, int y2, int r2)

Ограничения: -1000000000 £ x1, y1, x2, y2 £ 1000000000, 1 £ r1, r2 £ 1000000000.

Вход. Местоположения радаров (x₁, y₁) и (x₂, y₂), а также вычисленные ими расстояния до цели r₁ и r₂.

Выход. Количество возможных местоположений врага.

Пример входа

x1	x2	r1	x2	y2	r2
0	0	13	40	0	37
0	0	3	0	7	4
0	0	1	0	0	1

Пример выхода

2

1

-1

РЕШЕНИЕ

геометрия

Задача сводится к нахождению количества точек пересечения двух окружностей радиусами r₁, r₂, центры которых находятся в точках (x₁, y₁) и (x₂, y₂). Вычислим квадрат расстояния d2 между центрами окружностей.

Сначала рассмотрим случай, когда центры окружностй совпадают. Если r₁ = r₂, то цель может находиться в любом месте и следует вернуть -1. При r₁ ¹ r₂ измерения являются некорректными и выводим 0.

Если окружности касаются внешним или внутренним образом, то они имеют одну точку пересечения. Если из значений r₁, r₂, можно составить треугольник, то окружности имеют две точки пересечения. Условие того, что окружности не имеют точек пересечения, можно записать так:

(r₁ + r₂₎² < d2 или (r₁ – r₂₎² > d2

ПРОГРАММА

#include <stdio.h>

class RadarFinder

{

public:

int possibleLocations(int x1, int y1, int r1, int x2, int y2, int r2)

{

long long d2 = ((long long)x1 - x2) * (x1 - x2) +

((long long)y1 - y2) * (y1 - y2);

if ((x1 == x2) && (y1 == y2)) return (r1 == r2) ? -1 : 0;

if (((long long)r1 + r2) * (r1 + r2) == d2) return 1;

if (((long long)r1 - r2) * (r1 - r2) == d2) return 1;

if (((long long)r1 + r2) * (r1 + r2) < d2) return 0;

if (((long long)r1 - r2) * (r1 - r2) > d2) return 0;

return 2;

}

};